/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        // 使用 Lambda 表达式作为比较器
        auto compare = [](const ListNode* a, const ListNode* b) {
            return a->val > b->val; // 最小堆
        };
        priority_queue<ListNode*, vector<ListNode*>, decltype(compare)>
            min_heap;

        // 把每个链表的头节点放入堆中
        for (ListNode* head : lists) {
            if (head)
                min_heap.push(head);
        }

        // 构建结果链表
        ListNode dummy(0);
        ListNode* current = &dummy;

        while (!min_heap.empty()) {
            ListNode* node = min_heap.top();
            min_heap.pop();

            current->next = node;
            current = current->next;

            if (node->next)
                min_heap.push(node->next);
        }

        return dummy.next;
    }
};